#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define ALLOC_SIZE 8
#define LOOP 5
#define MAX_POOL_SIZE 1024 * 1024
#define BLOCK_SIZE 64

// 内存映射表
typedef struct memory_map_table
{
    char *p_block;
    int index;
    int used;
} Memory_Map_Table;

// 内存分配表
typedef struct memory_alloc_table
{
    char *p_start;
    int used;
    int block_start_index;
    int block_cnt;
} Memory_Alloc_Table;

typedef struct memory_pool
{
    char *memory_start;

    Memory_Map_Table *map_table;
    Memory_Alloc_Table *alloc_table;
    int total_size;
    int internal_total_size;
    int increment;
    int used_size;
    int block_size;
    int block_cnt;
    int alloc_cnt;
} Memory_Pool;

Memory_Map_Table *map_table_pos(Memory_Pool *pool)
{
    Memory_Map_Table *pm = (Memory_Map_Table*) (pool->memory_start + sizeof(Memory_Pool));
    return pm;
}

Memory_Alloc_Table *alloc_table_pos(Memory_Pool *pool)
{
    Memory_Alloc_Table* pm = (Memory_Alloc_Table*) (pool->memory_start + sizeof(Memory_Pool) + sizeof(Memory_Map_Table) * (pool->block_cnt));
    return pm;
}

char* memory_pos(Memory_Pool *pool)
{
    char* pm  = (char*) (pool->memory_start + sizeof(Memory_Pool) + (sizeof(Memory_Map_Table) + sizeof(Memory_Alloc_Table)) * pool->alloc_cnt);
    return (char*) pm;
}

Memory_Pool* memory_pool_init(int size, int increment)
{
    char *p = NULL;
    char *p_memory = NULL;
    Memory_Pool *pool = NULL;
    Memory_Alloc_Table *alloc_table = NULL;
    Memory_Alloc_Table *p_alloc_table = NULL;
    Memory_Map_Table *map_table = NULL;
    Memory_Map_Table *p_map_table = NULL;

    int block_cnt = 0;
    int all_size = 0;
    int i = 0;

    if (size < 0 || size > MAX_POOL_SIZE)
    {
        printf("memory_pool_init():invalid size(%d)\n", size);
        return NULL;
    }

    block_cnt = ((size + BLOCK_SIZE - 1) / BLOCK_SIZE);
    all_size = sizeof(Memory_Pool) + (sizeof(Memory_Map_Table) + sizeof(Memory_Alloc_Table)) * block_cnt + size;

    p = (char*) malloc(all_size);
    if (!p)
    {
        perror("memlloc failed.\n");
        return NULL;
    }
    
    memset(p, 0, all_size);
    pool = (Memory_Pool*)p;
    pool->block_cnt = block_cnt;
    pool->block_size = BLOCK_SIZE;
    pool->increment = increment;

    pool->internal_total_size = BLOCK_SIZE * block_cnt;
    pool->total_size = size;
    pool->used_size = 0;
    pool->memory_start = p;

    p_memory = memory_pos(pool);
    map_table = map_table_pos(pool);
    for (i = 0; i < block_cnt; i++)
    {
        p_map_table = (Memory_Map_Table *) ((char*) map_table + i * sizeof(Memory_Map_Table));
        p_map_table->index = 0;
        p_map_table->p_block = p_memory + i * BLOCK_SIZE;
        p_map_table->used = 0;
    }

    alloc_table = alloc_table_pos(pool);
    for (i = 0; i < block_cnt; i++)
    {
        p_alloc_table = (Memory_Alloc_Table *) ((char*) alloc_table + i * sizeof(Memory_Alloc_Table));
        p_alloc_table->block_cnt = 0;
        p_alloc_table->block_start_index = -1;
        p_alloc_table->p_start = NULL;
        p_alloc_table->used = 0;
    }
    
    printf("\n memory_pool_init:total size:%d, block cnt:%d, block size:%d\n\n", pool->total_size, pool->block_cnt, BLOCK_SIZE);
    return pool;
}


void * Memory_alloc(Memory_Pool *pool, int size)
{
    Memory_Alloc_Table *alloc_table = NULL;
    Memory_Alloc_Table *p_alloc_table = NULL;
    Memory_Map_Table *map_table = NULL;
    Memory_Map_Table *p_map_table = NULL;

    char *p_start = NULL;
    int need_block_cnt = 0;

    int block_cnt;
    int start_index = -1;
    int i;

    if (size <= 0)
    {
        printf("\n invalid size(%d)\n", size);
        return p_start;
    }

    if (size > pool->total_size)
    {
        printf("\n%d is more than total size.\n", size);
        return p_start;
    }

    if (size > pool->total_size - pool->used_size)
    {
        printf("free memroy(%d) is less than allocated(%d).\n", pool->total_size - pool->used_size, size);
        return NULL;
    }

    need_block_cnt = (size + BLOCK_SIZE - 1) / BLOCK_SIZE;
    map_table = map_table_pos(pool);

    start_index = -1;

    for (i = 0; i < pool->block_cnt; i++)
    {
        p_map_table = (Memory_Map_Table*) ((char*)map_table + i * sizeof(Memory_Map_Table));
        if (p_map_table->used)
        {
            block_cnt = 0;
            start_index = -1;
            continue;
        }
        
        if (start_index == -1)
        {
            start_index = i;
        }
        block_cnt ++;
        if (block_cnt == need_block_cnt)
        {
            break;
        }
        
        
    }
    
    if (start_index == -1)
    {
        printf("no available memory to used.\n");
        return NULL;
    }

    alloc_table = alloc_table_pos(pool);
    for (i = 0; i < pool->block_cnt; i++)
    {
        p_alloc_table = (Memory_Alloc_Table*)((char*) alloc_table + i * sizeof(Memory_Alloc_Table));
        if (0 == p_alloc_table->used)
        {
            break;
        }
        p_alloc_table = NULL;
        
    }
    
    if (p_alloc_table   == NULL)
    {
        return NULL;
    }
    
    p_map_table = (Memory_Map_Table*)((char*) map_table + sizeof(Memory_Map_Table) * start_index);
    p_alloc_table->p_start = p_map_table->p_block;
    p_alloc_table->block_start_index = p_map_table->index;
    p_alloc_table->block_cnt = block_cnt;
    p_alloc_table->used = 1;

    for (i = start_index; i < start_index + block_cnt; i++)
    {
        p_map_table = (Memory_Map_Table*) ((char*) map_table + i * sizeof(Memory_Map_Table));
        p_map_table->used = 1;
    }
    printf("\nalloc size:%d, block:(start:%d, end:%d, cnt:%d)\n", size, start_index, start_index + block_cnt);
    pool->alloc_cnt++;
    pool->used_size += size;
    return p_alloc_table->p_start;
    
}

void Memory_free(Memory_Pool *pool, void* memory)
{
    Memory_Alloc_Table *alloc_table = NULL;
    Memory_Alloc_Table *p_alloc_table = NULL;
    Memory_Map_Table *map_table = NULL;
    Memory_Map_Table *p_map_table = NULL;

    int i = 0;
    int block_start_index = 0;
    int block_cnt = 0;

    if (memory == NULL)
    {
        printf("memory free():memory is NULL.\n");
        return;
    }
    
    alloc_table = alloc_table_pos(pool);
    for (i = 0; i < pool->alloc_cnt; i++)
    {
       p_alloc_table = (Memory_Alloc_Table*) ((char*) alloc_table + i *sizeof(Memory_Alloc_Table));
       if (p_alloc_table->p_start == memory)
       {
            block_start_index = p_alloc_table->block_start_index;
            block_cnt = p_alloc_table->block_cnt;
       }
       
    }

    if (block_cnt == 0)
    {
        return;
    }
    
    map_table = map_table_pos(pool);
    printf("Block:free:start:%d,end%d,cnt:%d\n", block_start_index, block_start_index + block_cnt - 1, block_cnt);
    for (i = block_start_index; i < block_start_index + block_cnt; i++)
    {
        p_map_table = (Memory_Map_Table*)((char*) map_table + i * sizeof(Memory_Alloc_Table));
        p_map_table->used = 0;

    }
    p_alloc_table->used = 0;
    pool->used_size = block_cnt * BLOCK_SIZE;
}

void memory_pool_destroy(Memory_Pool* pool)
{
    if (pool == NULL)
    {
        printf("memory_pool_destroy:pool is NULL.\n");
        return;
    }
    
    free(pool);
    pool = NULL;
}

int main(void)
{
    Memory_Pool *pool = NULL;
    char *p1 = NULL;
    char *p2 = NULL;
    int i = 0;
    pool = memory_pool_init(1024, 512);
    if (!pool)
    {
        printf("memory_pool_init error.\n");
        return -1;
    }

    for (i = 0; i < 2; i++)
    {
        p1 = (char*) Memory_alloc(pool, ALLOC_SIZE);
        if (p1 == NULL)
        {
            printf("malloc failed.\n");
        } else
        {
            printf("malloc success.\n");

        }
        Memory_free(pool, p1);
    }
    
    
    return 0;
}